package cluster;

//import org.apache.log4j.Logger;

import app.ProgressListener;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;


public class Cluster<E extends Clusterable> {
	/**
	 * Logger for this class
	 */
	//private static final Logger logger = Logger.getLogger(Cluster.class);

	LookupTable<E> table;
	public Duster<E> root;
	ProgressListener listener;
	
	@SuppressWarnings("unchecked")
	public Cluster(ArrayList<E> list, float[] ratios, ProgressListener listener){

		this.listener = listener;
		ArrayList<Duster<E>> dusters = createDusters(list);
		
		float longest;
		try {
			longest = getLongestDistance(dusters);
			root = clusterUntil(dusters, ratios, longest);
		} catch (Exception e) {
			e.printStackTrace();
		}

//		if (logger.isInfoEnabled()) {
//			logger.info("Clustering done");
//		}
		root.sortAll();
	}
	
	public ArrayList<Duster<E>> createCluster(ArrayList<Duster<E>> list, int toSize, float maxSize, float mergeRatio) throws InstantiationException, IllegalAccessException{
		Duster.useLookup = false;
		while(list.size() > toSize){
//			if (logger.isInfoEnabled()) {
//				logger.info("createCluster(ArrayList<Duster<E>>, int, float, float) - clusters remaining: " + list.size());
//			}
			Key<E> key = getClosestPair(list);
			//if(key == null) logger.warn("Key == null");
			Duster<E> d1 = key.d1;
			Duster<E> d2 = key.d2;
			float dist = d1.getDistanceTo(d2);
			if(d1 == null || d2 == null){
//				if (logger.isDebugEnabled()) {
//					logger.debug("createCluster(ArrayList<Duster<E>>, int, float, float) - d2="
//									+ d2 + ", d1=" + d1 + ", key=" + key.d1.ID + " " + key.d2.ID + " dist=" + dist);
//				}
			}
			list.remove(d1);
			list.remove(d2);
			Duster<E> d = new Duster<E>(d1, d2);
			float maxDev = Math.max(d1.maxDev, d2.maxDev);
			if(d.maxDev < maxSize) {
				d.convertToLeaf();
				//table.removeDuster(d1);
				//table.removeDuster(d2);
			}
			else if(d.maxDev / maxDev < mergeRatio) d.assimilateChildren();
			//d.lookup = table;
			list.add(d);
			//table.addDistances(d, list);
		}
		return list;
	}
	
	
	//ratios = {2, 7, 21, 50}
	@SuppressWarnings("unchecked")
	public Duster<E> clusterUntil(ArrayList<Duster<E>> list, float[] ratios, float maxSize) throws InstantiationException, IllegalAccessException{
		Duster.useLookup = false;
		int startSize = list.size();
		for(int i = 0; i < ratios.length; i++){
			float max = maxSize / ratios[i];
			Key<E> key = null;
			float dist = 0;
			while(dist < max && list.size() > 1){
				if(listener != null) listener.progress("clusterUntil", (float)(startSize - list.size()) / (float)startSize);

				key = getClosestPair(list);
				Duster<E> d = new Duster<E>(key.d1, key.d2);
				dist = d.maxDist;
				if(dist < max){
					list.remove(key.d1);
					list.remove(key.d2);
					if(i == 0) 
						d.convertToLeaf();
					else{
						while(d.getHeight() > i) d.assimilateChild(d.getHighestChild());
						/*
						while(d.maxDist > maxSizes[i] && maxSizes[i] != -1){
							Key pair = getClosestPair(d.children);
							if(pair == null) break;
							d.children.remove(pair.d1);
							d.children.remove(pair.d2);
							ArrayList<Duster<E>> c = new ArrayList<Duster<E>>();
							if(pair.d1.isLeaf()) c.add(pair.d1);
							else c.addAll(pair.d1.children);
							if(pair.d2.isLeaf()) c.add(pair.d2);
							else c.addAll(pair.d2.children);
							d.addChild(new Duster<E>(c));
						}
						*/
					}
					list.add(d);
				}
				else{
					key.d1.parent = null;
					key.d2.parent = null;
				}
//				if (logger.isDebugEnabled()) {
//					logger.debug("clusterUntil(ArrayList<Duster<E>>, float[]) - list="
//									+ list.size() + ", dist=" + dist + ", max=" + max + ", i=" + i);
//				}

			}
		}
		if(list.size() == 1) return list.get(0);
		else return new Duster<E>(list);
		
	}
	
	@SuppressWarnings("unchecked")
	private ArrayList<Duster<E>> createDusters(ArrayList<E> list) {
		ArrayList<Duster<E>> n = new ArrayList<Duster<E>>(list.size());
		Iterator<E> i = list.iterator();
		while(i.hasNext()) n.add(new Duster<E>(i.next()));
		return n;
	}
	
	@SuppressWarnings("unchecked")
	private void setTable(ArrayList<Duster<E>> list, LookupTable table) {
		Iterator<Duster<E>> i = list.iterator();
		while(i.hasNext()) i.next().lookup = table;
	}
	
	@SuppressWarnings("unused")
	private void mergePair(ArrayList<Duster<E>> l) throws InstantiationException, IllegalAccessException{
		Iterator<Duster<E>> i1 = l.iterator();
		Iterator<Duster<E>> i2;
		Duster<E> cd1 = null, cd2 = null;
		float closest = Float.MAX_VALUE;
		while(i1.hasNext()){
			Duster<E> d1 = i1.next();
			i2 = l.iterator();
			while(i2.hasNext()){
				Duster<E> d2 = i2.next();
				float dist = d1.getDistanceTo(d2);
				if(dist < closest){
					closest = dist;
					cd1 = d1;
					cd2 = d2;
				}
			}
		}
		l.remove(cd1);
		l.remove(cd2);
		ArrayList<Duster<E>> c = new ArrayList<Duster<E>>();
		c.add(cd1);
		c.add(cd2);
		Duster<E> d = new Duster<E>(c);
		if(closest < 0.5) d.convertToLeaf();
		l.add(new Duster<E>(c));
		
	}
	
	public Duster<E> getByID(int id, ArrayList<Duster<E>> list){
		ListIterator<Duster<E>> i = list.listIterator();
		while(i.hasNext()){
			if(i.next().ID == id) return i.previous();
		}
		return null;
	}
	
	public Key<E> getClosestPair(ArrayList<Duster<E>> l) throws InstantiationException, IllegalAccessException{
		Iterator<Duster<E>> i1 = l.iterator();
		Iterator<Duster<E>> i2;
		Duster<E> cd1 = null, cd2 = null;
		float closest = Float.MAX_VALUE;
		while(i1.hasNext()){
			Duster<E> d1 = i1.next();
			i2 = l.iterator();
			while(i2.hasNext()){
				Duster<E> d2 = i2.next();
				if(d1.ID != d2.ID){
					float dist = d1.getDistanceTo(d2);
					if(dist < closest){
						closest = dist;
						cd1 = d1;
						cd2 = d2;
					}
				}
			}
		}
		if(cd1 == null || cd2 == null) return null;
		return new Key(cd1, cd2);
		
	}
	public float getLongestDistance(ArrayList<Duster<E>> l) throws InstantiationException, IllegalAccessException{
		Iterator<Duster<E>> i1 = l.iterator();
		Iterator<Duster<E>> i2;
		
		float longest = 0;
		while(i1.hasNext()){
			Duster<E> d1 = i1.next();
			i2 = l.iterator();
			while(i2.hasNext()){
				Duster<E> d2 = i2.next();
				if(d1.ID != d2.ID){
					float dist = d1.getDistanceTo(d2);
					if(dist > longest){
						longest = dist;
					}
				}
			}
		}
		return longest;
		
	}

	
	public void setMaxDiv(float devDiv){
		reorganizeDusters(root, devDiv);
	}
	
	public void reorganizeDusters(Duster<E> d, float devDiv){
		if(d.isLeaf()) return;
		float maxDev = d.maxDev / devDiv;
		boolean allBelow = false;
		while(!allBelow){
			allBelow = true;
			Iterator<Duster<E>> i = d.children.iterator();
			ArrayList<Duster<E>> nu = new ArrayList<Duster<E>>();
			while(i.hasNext()){
				Duster<E> next = i.next();
				if(next.maxDev > maxDev){
					nu.add(next);
					allBelow = false;
				}   	
			}
			Iterator<Duster<E>> k = nu.iterator();
			while(k.hasNext()) d.assimilateChild(k.next());
		}
		Iterator<Duster<E>> i = d.children.iterator();
		while(i.hasNext()) reorganizeDusters(i.next(), devDiv);
	}
}
